package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/partition-equal-subset-sum/
 */
public class P416 {

    //分割等和子集，0-1背包问题
    //物品为数组元素，物品的价值与重量均为元素的值
    //背包的容量为sum/2,(如果体积大于了sum/2就没有讨论的意义了)
    //dp[j]表示容量为j的背包能装的最大值
    public boolean canPartition(int[] nums) {
        int sum=0,target=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        target=sum/2;
        int[] dp=new int[target+1];
        for(int i=0;i<nums.length;i++){
            for(int j=target;j>=nums[i];j--){       //压缩版的dp,从后往前遍历，避免物品重复加入
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[target]==target){
            return true;
        }else{
            return false;
        }
    }
}
